import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-20
 * Time: 22:00
 */
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) {
            ans.add(0);
            return ans;
        }
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        int[] parent = new int[n]; // 记录每个节点的根节点
        Arrays.fill(parent, -1);
        // 找到距离 0 最远的 x
        int x = findLongestNode(0, adj, parent);
        // 找到距离 x 最远的 y
        int y = findLongestNode(x, adj, parent);
        // 那么 x, y 之间的路径就是这棵树中最远的一条路径

        // 找到 x, y 之间的路径
        List<Integer> list = new ArrayList<>();
        while (y != x) {
            list.add(y);
            y = parent[y];
        }
        list.add(x);
        // 最低的树的根节点一定在这条路径上, 如果路径长度为 偶数那么就有两个, 否则就是一个
        int len = list.size();
        ans.add(list.get(len/2));
        if (len % 2 == 0) {
            ans.add(list.get(len/2 - 1));
        }
        return ans;
    }


    /**
     *  找到一个距离该节点最远的节点
     */
    public int findLongestNode(int root, List<Integer>[] adj, int[] parent) {
        int count = adj.length;
        int ans = -1;
        boolean[] visited = new boolean[count];
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(root);
        visited[root] = true; // 记录哪个节点已经被遍历过了, 防止死循环
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            ans = cur;
            for (Integer x: adj[cur]) {
                if (!visited[x]) {
                    queue.offer(x);
                    parent[x] = cur;
                    visited[x] = true;
                }
            }
        }
        return ans;
    }


    /**
     *  方法二: 拓扑排序
     *  每次将 图中 所有度为 1 的节点删除 (使用队列)
     *  然后将对应连接的节点的 度数 - 1
     *  如果该节点的度数也 减为 1, 就也加入队列
     *  最终剩下的 1 个 或者 2 个 节点就是 能使树最低的 根节点
     */
    public List<Integer> findMinHeightTrees2(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) {
            ans.add(0);
            return ans;
        }
        // 每个节点的度
        int[] degrees = new int[n];
        // 邻接矩阵
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        int remainNodes = n;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (degrees[i] == 1) {
                queue.add(i);
            }
        }
        while (remainNodes > 2) {
            int size = queue.size();
            remainNodes -= size;
            for (int i = 0; i < size; i++) {
                int node = queue.remove();
                for (Integer near: adj[node]) {
                    degrees[near]--;
                    if (degrees[near] == 1) {
                        queue.add(near);
                    }
                }
            }
        }
        while (!queue.isEmpty()) {
            ans.add(queue.remove());
        }
        return ans;
    }




    ArrayList<Integer> ans = new ArrayList<>();
    ArrayList<Integer>[] graph;
    int[] f1;
    int[] f2;
    int[] g;

    // ☆☆☆☆☆ 树形dp
    public List<Integer> findMinHeightTrees3(int n, int[][] edges) {
        graph = new ArrayList[n];
        Arrays.setAll(graph, i -> new ArrayList<>());
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }

        // 状态定义：当前节点（包括当前节点）到叶子节点的最大路径长度，按方向（父节点方向↑、子树方向↓）划分
        f1 = new int[n]; // 子树方向↓ 的最大值
        f2 = new int[n]; // 子树方向↓ 的次大值（用于父节点方向↑ 的最大值的计算）
        g = new int[n]; // 父节点方向↑ 的最大值

        // 状态转移：分别进行两次 dfs，先下↓再上↑
        dfsDown(0, -1);
        dfsUp(0, -1);

        for (int i = 0, min = n - 1; i < n; i++) {
            // 当前节点（包括当前节点）到叶子节点的最大路径长度 = max （父节点方向↑，子树方向↓）
            int cur = Math.max(f1[i], g[i]);
            if (cur < min) {
                min = cur;
                ans.clear();
                ans.add(i);
            } else if (cur == min) {
                ans.add(i);
            }
        }

        return ans;
    }

    private int dfsDown(int u, int fa) {
        for (Integer v : graph[u]) {
            if (v == fa) {
                continue;
            }
            int sub = dfsDown(v, u) + 1;
            // 更新最大次大值
            if (sub > f1[u]) {
                f2[u] = f1[u];
                f1[u] = sub;
            } else if (sub > f2[u]) {
                f2[u] = sub;
            }
        }
        return f1[u];
    }

    private void dfsUp(int u, int fa) {
        for (Integer v : graph[u]) {
            if (v == fa) {
                continue;
            }
            // 小技巧：为避免对 fa 节点为空的处理，将「用 fa 来更新 u」调整为「用 u 来更新 v」。
            g[v] = Math.max(g[v], 1 + g[u]); // ① 父节点的「父节点方向」最大值 + 1
            g[v] = Math.max(g[v], 1 +
                    (f1[v] + 1 == f1[u] ?
                            f2[u] : // ② 父节点的「子树节点方向」次大值 + 1 （父节点的「子树节点方向」最长路径经过当前节点 v）
                            f1[u] // ③ 父节点的「子树节点方向」最大值 + 1 （父节点的「子树节点方向」最长路径不经过当前节点 v）
                    ));

            dfsUp(v, u);
        }
    }

}
